◀ Prev · Parts · Full · Next ▶

where S is the number of different sizes, n is the number of different items, and the size of the smallest item is eB. In particular, if e ≥ 1/n and h=1, the algorithm finds a solution with at most LOPT+1 bins in time: O ( S 8 log ⁡ ⁡ S log 2 ⁡ ⁡ n + S 4 n log ⁡ ⁡ S log ⁡ ⁡ n ) {\displaystyle O\left(S^{8}\log {S}\log ^{2}{n}+S^{4}n\log {S}\log {n}\right)} . A randomized variant of this algorithm runs in expected time:

O ( S 7 log ⁡ ⁡ S log 2 ⁡ ⁡ ( S n e h ) + S 4 n log ⁡ ⁡ S h log ⁡ ⁡ ( S n e h ) ) {\displaystyle O\left(S^{7}\log {S}\log ^{2}({\frac {Sn}{eh}})+{\frac {S^{4}n\log {S}}{h}}\log({\frac {Sn}{eh}})\right)} .

Karmarkar and Karp further developed a way to round the fractional LP into an approximate solution to the integral LP; see Karmarkar-Karp bin packing algorithms. Their proof shows that the additive integrality gap of this LP is in O(log2(n)). Later, Hoberg and Rothvosscite-ref-3-10-0[10] improved their result and proved that the integrality gap is in O(log(n)). The best known lower bound on the integrality gap is a constant Ω(1). Finding the exact integrality gap is an open problem.

◀ Prev · Parts · Full · Next ▶